package everyday;

import common.Node;

/**
 * @author zhangmin
 * @create 2022-05-05 10:03
 * 剑指 Offer 36. 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 *
 * 思路：
 * 二叉搜索树的中序遍历就是有序的，所以直接按照中序遍历位置进行处理
 * 需要记录
 */
public class treeToDoublyList_offer36 {
    Node head=null,pre=null;
    void minOrder(Node root){
        if (root==null)return;
        minOrder(root.left);
        //中序遍历位置
        if (head==null){
            //找到第一个节点
            head=root;
        }else {
            pre.right=root;
            root.left=pre;
        }
        pre= root;
        minOrder(root.right);
    }
    public Node treeToDoublyList(Node root) {
        if (root==null) return null;
        minOrder(root);
        pre.right= head;
        head.left=pre;
        return head;
    }
}
